Disjoint Sparse Table
長さNの静的な値の列が与えられた時に、前処理O(NlogN)で、その列の上の区間に対する演算がO(1)で計算できるようになるデータ構造
演算に要求される条件
結合則
:
$ (a * b) * c = a * (b * c)
単位元や逆元は必要ない
加算のような逆元のある演算についてはこれを使う必要はない
累積和
を使って構築O(N)で同じことができるから
逆元のない乗算などで
左右から累積積
で
一つ除き積
を実現できる
これをたくさんの累積積を組み合わせて任意の区間の積を計算できるようにしたのがDisjoint Sparse Table
Disjoint Sparse Table と セグ木に関するポエム - noshi91のメモ
Sparse Table